/**
 * 44. 通配符匹配
 * https://leetcode-cn.com/problems/wildcard-matching/
 */
public class Solutions_44 {
    public static void main(String[] args) {
//        String s = "aa", p = "a";  // output: false
        // 解释: "a" 无法匹配 "aa" 整个字符串。

//        String s = "aa", p = "*";  // output: true
        // 解释: '*' 可以匹配任意字符串。

//        String s = "cb", p = "?a";  // output: false
        // 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

//        String s = "abab", p = "ab*";  // output: true

//        String s = "adceb", p = "*a*b";  // output: true
        // 解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

        String s = "acdcb", p = "a*c?b";  // output: false

        boolean result = isMatch(s, p);
        System.out.println(result);
    }

    public static boolean isMatch(String s, String p) {
        char[] sarr = s.toCharArray();
        char[] parr = p.toCharArray();
        int slen = sarr.length, plen = parr.length;
        // dp[2][2] = true，表示字符串 s 里前 2 个字符与字符串 p 里前 2 个字符的匹配结果为 true
        boolean[][] dp = new boolean[slen + 1][plen + 1];
        dp[0][0] = true;
        // 填充 * 字符
        for (int i = 1; i <= plen; i++) {
            if (parr[i - 1] == '*') {
                dp[0][i] = true;
            } else {
                break;
            }
        }
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= plen; j++) {
                if (parr[j - 1] == '*') {
                    // 例：aaa 与 aaa* 匹配时，可以继承 aaa 与 aaa（即 * 表示空字符）
                    dp[i][j] = dp[i][j] || dp[i][j - 1];

                    // 例：abab 与 ab* 的结果（即 * 表示一个字符）
                    dp[i][j] = dp[i][j] || dp[i - 1][j];

                } else if (sarr[i - 1] == parr[j - 1] || parr[j - 1] == '?') {
                    // 两个字符相同的情况
                    // aab 与 aa? 的结果，继承 aa 与 aa 的结果
                    dp[i][j] = dp[i - 1][j - 1];
                }
            }
        }
        return dp[slen][plen];
    }
}
